176E - Archaeology - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, q;
struct Graph {
    vector<pair<int, int>> e[MAXN];
    int dfn[MAXN], idf[MAXN], dcnt;
    int fa[MAXN][22];
    int dep[MAXN];
    long long dis[MAXN];
    void add(int u, int v, int w) {
        e[u].push_back({v, w});
        e[v].push_back({u, w});
    }
    void dfs(int u, int pre) {
        fa[u][0] = pre;
        for (int i = 1; i <= 20; i++) 
            fa[u][i] = fa[fa[u][i - 1]][i - 1];
        dep[u] = dep[pre] + 1;
        dfn[u] = ++dcnt;
        idf[dcnt] = u;
        for (auto p : e[u]) if (p.first != pre) {
            int v = p.first, w = p.second;
            dis[v] = dis[u] + w;
            dfs(v, u);
        }
    }
    int lca(int u, int v) {
        if (dep[u] < dep[v]) swap(u, v);
        for (int i = 20; i >= 0; i--)
            if (dep[fa[u][i]] >= dep[v]) u = fa[u][i];
        if (u == v) return u;
        for (int i = 20; i >= 0; i--)
            if (fa[u][i] != fa[v][i]) u = fa[u][i], v = fa[v][i];
        return fa[u][0];
    }
    long long dist(int u, int v) {
        return dis[u] + dis[v] - 2 * dis[lca(u, v)];
    }
} g;
struct SegmentTree {
    struct Node {
        int fst, lst;
        long long sum;
    } t[MAXN << 2];
    #define lc (i << 1)
    #define rc (i << 1 | 1)
    void pushUp(int i) {
        if (!t[lc].fst) {
            t[i] = t[rc];
        } else if (!t[rc].fst) {
            t[i] = t[lc];
        } else {
            t[i].sum = t[lc].sum + t[rc].sum + g.dist(g.idf[t[lc].lst], g.idf[t[rc].fst]);
            t[i].fst = t[lc].fst;
            t[i].lst = t[rc].lst;
        }
    }
    void set(int d, int v, int i = 1, int l = 1, int r = n) {
        if (l == r) {
            if (v == 0) {
                t[i].fst = t[i].lst = 0;
            } else {
                t[i].fst = t[i].lst = l;
            }
            return;
        }
        int mid = (l + r) >> 1;
        if (d <= mid) set(d, v, lc, l, mid);
        else set(d, v, rc, mid + 1, r);
        pushUp(i);
    }
} st;
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        g.add(u, v, w);
    }
    g.dfs(1, 0);
    scanf("%d", &q);
    while (q--) {
        char op; scanf(" %c", &op);
        if (op == '+') {
            int u; scanf("%d", &u);
            st.set(g.dfn[u], 1);
        }
        if (op == '-') {
            int u; scanf("%d", &u);
            st.set(g.dfn[u], 0);
        }
        if (op == '?') {
            printf("%lld\n", (st.t[1].sum + g.dist(g.idf[st.t[1].fst], g.idf[st.t[1].lst])) / 2);
        }
    }
    return 0;
}//6287838605153792925